AlgoView Lab | DFS Tree Traversal

Depth-First Search (DFS)

DFS is an algorithm for traversing or searching tree or graph data structures. The algorithm starts at the root node and explores as far as possible along each branch before backtracking.

Key Characteristics:

Uses a Stack (either explicitly or via the call stack in recursion).
Time Complexity: $O(V + E)$ where $V$ is vertices and $E$ is edges.
Space Complexity: $O(h)$ where $h$ is the maximum height of the tree.

1. Iterative Approach (Using std::stack)

// Recommended for very deep trees to avoid stack overflow
void dfsIterative(Node* root) {
    if (!root) return;
    std::stack<Node*> s;
    s.push(root);

    while (!s.empty()) {
        Node* curr = s.top();
        s.pop();

        std::cout << curr->val << " ";

        // Push right first so left is processed first (LIFO)
        if (curr->right) s.push(curr->right);
        if (curr->left) s.push(curr->left);
    }
}

2. Recursive Approach

// The most common and concise way
void dfsRecursive(Node* node) {
    if (!node) return;

    std::cout << node->val << " "; // Pre-order visit
    
    dfsRecursive(node->left);
    dfsRecursive(node->right);
}